import collections
import heapq


class FreqStack(object):

    def __init__(self):
        self.st = []
        self.c = collections.defaultdict(int)
        self.index = 0

    def push(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.c[val] += 1
        num = self.c[val]
        heapq.heappush(self.st, [- num, self.index, val])
        self.index -= 1


    def pop(self):
        """
        :rtype: int
        """
        _, _, val = heapq.heappop(self.st)
        self.c[val] -= 1
        return val
